Categories of profunctors

Composing profunctors(4)
V-profunctor composition(1)

The composite \(\mathcal{X}\overset{\phi;\psi}\nrightarrow \mathcal{Z}\) of two \(\mathcal{V}\) profunctors, \(\mathcal{X}\overset{\phi}\nrightarrow\mathcal{Y}\) and \(\mathcal{Y}\overset{\psi}\nrightarrow\mathcal{Z}\)

\((\phi;\psi)(x,z) = \bigvee_Y(\phi(x,y)\otimes\psi(y,z))\)

Linked by

Composing Bool-profunctors(1)

  • Need a formula for composing two feasibility relations in series.

  • Suppose \(P,Q,R\) are cities (preorders) and there are bridges (hence, feasibility matrices).

  • The feasibility matrices are:

    \(\textcolor{blue}{\phi}\) a b c d e
    N T F T F F
    E T F T F T
    W T T T T F
    S T T T T T
    \(\textcolor{red}{\psi}\) x y
    a F T
    b T T
    c F T
    d T T
    e F F

  • Feasibility from \(P\) to \(R\) means there is a way-point in Q which is both reachable from \(p \in P\) and can reach \(r \in R\).

  • Composition is a union \((\phi;\psi)(p,r):= \bigvee_Q \phi(p,q)\land \psi(q,r)\).

  • But this is tantamount to matrix multiplication which gives us the result matrix:

    \(\phi;\psi\) x y
    N F T
    E F T
    W T T
    S T T
Exercise 4-22(2)

Consider the following Cost profunctors \(\textcolor{blue}{\phi},\textcolor{red}{\psi}\) \[\begin{tikzcd}[ampersand replacement=\&] A \arrow[d, "3"', bend right] \& B \arrow[l, "2"', bend right] \arrow[d, "5", bend left] \arrow[r, "11", blue, dotted, bend left] \& x \arrow[rr, "3", bend left] \arrow[rd, "4", bend left] \& \& z \arrow[ld, "4", bend left] \arrow[r, "4", red,dotted, bend left] \arrow[rd, red, "4", dotted, bend right] \& p \arrow[r, "2", bend left] \& q \arrow[d, "2", bend left] \\ C \arrow[ru, "3"] \& D \arrow[l, "4", bend left] \arrow[rr, blue, "9", dotted, bend right] \& \& y \arrow[lu, "3", bend left] \arrow[rrr, red, "0", dotted, bend right=49] \& \& d \arrow[u, "1", bend left] \& r \arrow[l, "1", bend left] \end{tikzcd}\]

Fill in the matrix for the composite profunctor.

Solution(1)
\(\phi;\psi\) p q r s
A 23 25 21 22
B 17 19 15 16
C 20 22 18 19
D 11 13 9 10
The categories V-Prof and Feas(12)
V-profunctor category(1)

The category \(\mathbf{Prof}_\mathcal{V}\), given a skeletal quantale \(\mathcal{V}\)

Linked by

The category Feas(1)

The category Feas

Instantiate a \(\mathbf{Prof}_\mathcal{V}\) category with \(\mathcal{V}=\mathbf{Bool}\)

The unit profunctor(1)
Unitality of unit profunctor(2)
Proof(1)

  • Due to skeletality, we need to show for all inputs that \(\phi \leq U_P;\phi\) and \(U_P;\phi \leq \phi\) (the second equality to show is done similarly).

  • Forward direction

    • \(\phi(p,q) = I \otimes \phi(p,q)\)

    • \(\leq P(p,p) \otimes \phi(p,q)\)

      • This is because \(\forall p \in P:\) \(I \leq P(p,p)\) (a constraint of a \(\mathcal{V}\) category), the reflexivity of \(\leq\) for \(\phi(p,q)\), and the monotonicity of \(\otimes\).

    • \(\leq \underset{p' \in P}\bigvee(P(p,p') \otimes \phi(p',q))\)

      • The join is a least upper bound, and the LHS is an element of the set being joined over (the case where \(p=p'\)).

    • \(= (U_P;\phi)(p,q)\)

  • Reverse direction

    • Need to show \(\underset{p' \in P}\bigvee(P(p,p')\otimes \phi(p',q)) \leq \phi(p,q)\)

    • Show that this property holds for each \(p' \in P\) - given the join is a least upper bound, it will also be less than or equal to \(\phi(p,q)\)

    • \(P(p,p')\otimes\phi(p',q) = P(p,p')\otimes\phi(p',q)\otimes I\)

    • \(\leq P(p,p')\otimes \phi(p',q)\otimes Q(q,q)\)

      • \(\forall p:\) \(I \leq P(p,p)\) (a constraint of a \(\mathcal{V}\) category) and the monotonicity of \(\otimes\).

    • \(\leq\phi(p,q)\)

The unit profunctor is unital, i.e. for any profunctor \(P \overset{\phi}\nrightarrow Q\): \(U_P;\phi = \phi = \phi; U_Q\)

Linked by

Exercise 4-26(2)

Choose a nontrivial Cost-category \(\mathcal{X}\) and draw a bridge-style diagram of the unit profunctor \(\mathcal{X} \overset{U_\mathcal{X}}\nrightarrow \mathcal{X}\)

Solution(1)

becomes

Exercise 4-30(2)

  1. Justify all steps the proof of the unitality of unit profunctors.

  2. In the case of \(\mathcal{V}=\mathbf{Bool}\) show each step in the forward direction is actually an equality. NOCARD

Solution(1)

  1. Done, see the proof

    • \(\forall p: P(p,p)=true\) for a Bool-enriched category, because that is the only option for \(I=true\leq P(p,p)\)

      • \(true \land x = x\)

    • If \(\phi(p,q)\):

      • then at least one element of the set being joined over is true (where \(p=p'\) such that \(P(p,p')\land \phi(p',q) = true\)), and the least upper bound of such a set is \(true\)

    • Else:

      • Then every element of that set is \(false\) such that the join is also \(false\).

        • If \(p\leq p'\), it fails because of the second conjunct (consider the constraint on profunctors: we are demanding equal or more resources than something we know fails)

        • If \(p \not \leq p'\), it fails because of the first conjunct. In a Bool-category \(P\), \(P(a,b)\) iff \(a \leq b\).

Exercise 4-31(2)

Prove that the serial composition of profunctors, \(\mathcal{X}\overset{\phi}\nrightarrow\mathcal{Y}\) and \(\mathcal{Y}\overset{\psi}\nrightarrow\mathcal{Z}\), is associative.

Solution(1)

This is tantamount to the quantale matrix multiplication being associative, which was shown in Exercise 2.104.

Fun profunctor facts - companions, conjoints, collages(11)
Companion and conjoint(1)

The companion and conjoint of a \(\mathcal{V}\) functor, \(\mathcal{P}\xrightarrow{F}\mathcal{Q}\)

  • Companion, denoted \(\mathcal{P}\overset{\hat F}\nrightarrow \mathcal{Q}\), is defined \(\hat{F}(p,q):=\mathcal{Q}(F(p),q)\)

  • Conjoint, denoted \(\mathcal{Q}\overset{\check{F}}\nrightarrow\mathcal{P}\)

Linked by

V-adjunction(1)

A \(\mathcal{V}\) adjunction.

A pair of \(\mathcal{V}\) functors, \(\mathcal{P}\overset{F}{\underset{G}\rightleftarrows} \mathcal{Q}\) such that: \(\forall p\in \mathcal{P}, q \in \mathcal{Q}: \mathcal{P}(p,G(q)) \cong \mathcal{Q}(F(p),q)\)

V-profunctor collage(1)

The collage of a \(\mathcal{V}\) profunctor, \(\mathcal{X}\overset{\phi}\nrightarrow \mathcal{Y}\)

  • A \(\mathcal{V}\) category, denoted \(\mathbf{Col}(\phi)\)

    • \(Ob(\mathbf{Col}(\phi)):=\)\(Ob(\mathcal{X})\sqcup Ob(\mathcal{Y})\)

    • \(\mathbf{Col}(\phi)(a,b) :=\) \(\begin{cases}\mathcal{X}(a,b) & a,b \in \mathcal{X} \\ \phi(a,b)& a \in \mathcal{X}, b \in \mathcal{Y} \\ \varnothing & a \in \mathcal{Y}, b \in \mathcal{X} \\ \mathcal{Y}(a,b) & a,b \in \mathcal{Y} \end{cases}\)

  • There are obvious functors \(\mathcal{X}\xrightarrow{i_\mathcal{X}}\mathbf{Col}(\phi)\) and \(\mathcal{Y}\xrightarrow{i_\mathcal{Y}}\mathbf{Col}(\phi)\) sending each object to “itself" called collage inclusions

Linked by

Companion and conjoint of identity(1)

  • For any preorder \(\mathcal{P}\), there is an identity functor \(\mathcal{P}\xrightarrow{id}\mathcal{P}\)

  • Its companion and conjoint agree: \(\hat{id}=\check{id}=\mathcal{P}\overset{U_\mathcal{P}}\nrightarrow \mathcal{P}\) equivalent to the unit profunctor.

Companion and conjoint of addition(1)

  • Consider the addition function on real numbers.

  • It is monotonic, since \((a,b,c)\leq(a',b',c')\) means \(a+b+c\leq a'+b'+c'\)

  • Therefore it has a companion and a conjoint

    • The companion \(\mathbb{R}\times\mathbb{R}\times\mathbb{R}\overset{\hat +}\nrightarrow \mathbb{R}\) sends (a,b,c,d) to true iff \(a+b+c\leq d\).

Linked by

Example 4-43 todo(1)

TODO

Exercise 4-36(2)

Check that the companion \(\hat{id}\) of the identity functor is actually the unit profunctor.

Solution(1)

TODO

Exercise 4-38(1)

Considering the addition example, what is the conjoint of this addition function?

Solution(0)

TODO

Exercise 4-41(1)

Let \(\mathcal{V}\) be a skeletal quantale and \(\mathcal{P}\overset{F}{\underset{G}\rightleftarrows} \mathcal{Q}\) be \(\mathcal{V}\) functors. Show that \(F \dashv G\) iff the companion of the former equals the conjoint of the latter, i.e. \(\hat F = \check G\)

Solution(0)

TODO

Exercise 4-44(1)

Draw a Hasse diagram for the collage of the profunctor:

Solution(0)

TODO